package com.nanbei.dp;

/**
 * @ClassDescription:  旅行商问题 （动态规划）
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/10 16:48
 */
public class TravellingSalesmanProblem {


    /*
        北京->
        上海->
        武汉->
        西安->

        4x3x2 = 24
        5x4x3x2 = 120
        ...
        (n-1)!
        北京->上海->
                  武汉->西安->北京
                  西安->武汉->北京
             西安->
                  上海->武汉->北京
                  武汉->上海->北京
             武汉->
                  上海->西安->北京
                  西安->上海->北京

         0： 北京
         1： 上海
         2： 西安
         3： 武汉

              0  1  2  3
          0  {0, 1, 2, 3}
          1  {1, 0, 6, 4}
          2  {2, 6, 0, 5}
          3  {3, 4, 5, 0}

          d(出发城市, 剩余城市集合) ==> 从出发城市开始，走完剩余城市，花费的最少代价
          d(0,1|2|3) => g[0][1] + d(1,2|3) => g[1][3] + d(3,2) => g[3][2] + d(2,空)
                                                                            g[2][0]
                                           => g[1][2] + d(2,3) => g[2][3] + d(3,空)
                                                                            g[3][0]
                        g[0][2] + d(2,1|3) => g[2][1] + d(1,3) => g[1][3] + d(3,空)
                                                                            g[3][0]
                                           => g[2][3] + d(3,1) => g[3][1] + d(1,空)
                                                                            g[1][0]
                        g[0][3] + d(3,1|2) => g[3][1] + d(1,2) => g[1][2] + d(2,空)
                                                                            g[2][0]
                                           => g[3][2] + d(2,1) => g[2][1] + d(1,空)
                                                                            g[1][0]
                0   1   2   3    4   5    6    7     j 剩余城市集合
                0   1   2   1|2  3   1|3  2|3  1|2|3
           0
           1
           2
           3
           i 出发城市

           000 没城市  0
           001 1号    1
           010 2号    2
           100 3号    4
           011 1和2   3
           101 1和3   5
           110 2和3   6
           111 1和2和3 7

          出发城市 i
          剩余城市集合 j
            遍历 j 时的变量 k （剩余的某一个城市)
          d(i, j) => min(
                        g[i][k] + d(k, j去掉k)
                        g[i][k] + d(k, j去掉k)
                        g[i][k] + d(k, j去掉k)
                    )
          d(k,空) => 从k回到起点 => g[k][i]


          d(0,1|2) => g[0][1] + d(1,2)
                   => g[0][2] + d(2,1)
          d(1,1|2)
          d(2,1|2)
          d(3,1|2) => g[3][1] + d(1,2)
                   => g[3][2] + d(2,1)
     */

}
